November 02, 2020
In mathematics, we are representing the negative numbers using the minus sign -. In computer hardware, there's no such thing. Only 0 and 1, so we needed to find a way to encode our negative numbers in binary form without using an extra symbol.
There are several ways to encode a negative number into binary, but the main technique that is used nowadays by processors is called two's complement.
Let's take a 4-bits chuck of memory as an example. In regular encoding, as seen above, this chunk can store numbers from 0 (0000 in binary) to 15 (1111 in binary). With 4 bits, we can only store 16 different values, so the idea with the two's complement method is to shift the values in order to represent numbers from -8 to 7 instead - so that we can represent negative numbers.
The two's complement method goes like this: for each strictly positive number, you can find it's negative counter-part by inverting all its bits and adding one. For example:
| Number (base 10) | 4-bits binary | Negative (base 10) | Two's complement |
| 1 | 0001 | -1 | 1110 + 0001 = 1111 |
| 2 | 0010 | -2 | 1101 + 0001 = 1110 |
| 3 | 0011 | -3 | 1100 + 0001 = 1101 |
| 7 | 0111 | -7 | 0110 + 0001 = 0111 |
This also works the other way around:
| Number (base 10) | 4-bits binary | Negative (base 10) | Two's complement |
| -1 | 1111 | 1 | 0000 + 0001 = 0001 |
| -2 | 1110 | 2 | 0001 + 0001 = 0010 |
| -3 | 1101 | 3 | 0010 + 0001 = 0011 |
| -7 | 1001 | 7 | 0110 + 0001 = 0111 |
There are two special cases, though: 0 and -8:
| Number (base 10) | 4-bits binary | Two's complement |
| 0 | 0000 | 0000 |
| -8 | 1000 | 1000 |
More formally, the two's complement b of a binary number a encoded using n bits is the binary number such that a + b = 2^n with n the number of bits that encodes a and b. Thus, b = 2^n - a, and we can find our two special cases:
| 4-bit number a | Two's complement (base 10) | Two's complement on 5-bits | 4-bit Two's complement |
| 0000 | 16 - 0 = 16 | 10000 - 00000 = 10000 | 0000 |
| 1000 | 16 - 8 = 8 | 10000 - 01000 = 01000 | 1000 |
As you can see, overflowing bits are thrown away (the fifth bit cannot be stored as we are using 4 bits to stored our numbers).